package num120;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/4/14 0:13
 * @Desc :
 */
public class Solution {
  public int minimumTotal0(List<List<Integer>> triangle) {
    int height = triangle.size();
    int[][] status = new int[height][];

    status[0] = new int[1];
    status[0][0] = triangle.get(0).get(0);

    for (int i = 1; i < height; i++) {
      status[i] = new int[triangle.get(i).size()];
      for (int j = 0; j < triangle.get(i).size(); j++) {
        if (j == 0) {
          status[i][j] = triangle.get(i).get(j) + status[i - 1][j];
        } else if (j == triangle.get(i).size() - 1) {
          status[i][j] = triangle.get(i).get(j) + status[i - 1][j - 1];
        } else {
          status[i][j] = triangle.get(i).get(j) + Math.min(status[i - 1][j], status[i - 1][j - 1]);
        }
      }
    }
    int res = status[height - 1][0];
    for (int i = 1; i < status[height - 1].length; i++) {
      res = Math.min(res, status[height - 1][i]);
    }
    return res;
  }

  public int minimumTotal1(List<List<Integer>> triangle) {
    int size = triangle.size();
    int[][] status = new int[size][];
    status[size - 1] = new int[size];
    for (int i = 0; i < size; i++) {
      status[size - 1][i] = triangle.get(size - 1).get(i);
    }
    for (int i = size - 2; i >= 0; i--) {
      status[i] = new int[i + 1];
      for (int j = 0; j < i + 1; j++) {
        status[i][j] = triangle.get(i).get(j) + Math.min(status[i + 1][j], status[i + 1][j + 1]);
      }
    }
    return status[0][0];
  }

  public int minimumTotal(List<List<Integer>> triangle) {
    int size = triangle.size();
    int[] status = new int[size];
    // 将最低一层的值，直接放入状态数组中
    for (int i = 0; i < triangle.get(size - 1).size(); i++) {
      status[i] = triangle.get(size - 1).get(i);
    }
    // 遍历每一行的每个值，更新状态方程
    for (int i = size - 2; i >= 0; i--) {
      for (int j = 0; j < i + 1; j++) {
        status[j] = Math.min(status[j], status[j + 1]) + triangle.get(i).get(j);
      }
    }
    return status[0];
  }


  public static void main(String[] args) {
    List<List<Integer>> triangle = new ArrayList<>();
    triangle.add(List.of(2));
    triangle.add(List.of(3, 4));
    triangle.add(List.of(6, 5, 7));
    triangle.add(List.of(4, 1, 8, 3));
    System.out.println(new Solution().minimumTotal(triangle));
  }
}
